package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import java.util.*

/*
 https://leetcode.cn/problems/binary-tree-right-side-view/
 https://programmercarl.com/0102.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86.html

 199. 二叉树的右视图
 示例 1：
 输入：root = [1,2,3,null,5,null,4]
 输出：[1,3,4]

 示例 2：
 输入：root = [1,2,3,4,null,null,null,5]
 输出：[1,3,4,5]

 示例 3：
 输入：root = [1,null,3]
 输出：[1,3]

 示例 4：
 输入：root = []
 输出：[]

 */
class leetcode_199 {
    @Test
    fun test_1() {
        val n1 = TreeNode(1)
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n5 = TreeNode(5)
        val n4 = TreeNode(4)

        n1.left = n2
        n1.right = n3
        n2.right = n5
        n3.right = n4
        val actual = rightSideView(n1)
        val expect = arrayListOf(1, 3, 4)
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    @Test
    fun test_2() {
        val n1 = TreeNode(1)
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n5 = TreeNode(5)
        val n4 = TreeNode(4)

        n1.left = n2
        n1.right = n3
        n2.left = n4
        n4.left = n5
        val actual = rightSideView(n1)
        val expect = arrayListOf(1, 3, 4, 5)
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    @Test
    fun test_3() {
        val n1 = TreeNode(1)
        val n3 = TreeNode(3)
        n1.right = n3
        val actual = rightSideView(n1)
        val expect = arrayListOf(1, 3)
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    @Test
    fun test_4() {
        val actual = rightSideView(null)
        val expect = ArrayList<Int>()
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    private fun rightSideView(root: TreeNode?): List<Int> {
        // 层序遍历，判断是否遍历到单层的最后面的元素，如果是，就放进result数组中，随后返回result就可以了。
        // S - N
        // T - N
        val result: ArrayList<Int> = ArrayList<Int>()
        if (null == root) {
            return result
        }
        var size: Int
        val queue: LinkedList<TreeNode> = LinkedList<TreeNode>()
        queue.offer(root)
        while (!queue.isEmpty()) {
            size = queue.size
            for (i in 1..size) {
                val node = queue.poll()
                if (i == size) {
                    result.add(node.`val`)
                }
                node.left?.let { queue.offer(it) }
                node.right?.let { queue.offer(it) }
            }
        }
        return result
    }
}